package LeetCode.Medium;

import java.util.ArrayList;
import java.util.Arrays;

public class Question010 {
    public static void main(String[] args) throws Exception {
        int[] leastNumbers = new Question010().getLeastNumbers(new int[]{0, 2, 1, 1}, 1);
        for (int leastNumber : leastNumbers) {
            System.out.print(leastNumber);
        }
    }
    public int[] getLeastNumbers(int[] arr, int k) throws Exception {
//        Arrays.sort(arr);
//        int[] num = new int[k];
//        for (int i = 0; i < k; i++) {
//            num[i] = arr[i];
//        }

        if(k > arr.length || k<=0){
            throw new Exception();
        }

        findKthSmallest(arr, 0,arr.length-1, k-1);
//        ArrayList<Integer> ret = new ArrayList<>();
//        for (int val : num) {
//            if(val <= kthSmallest && ret.size()<k){
//
//            }
//        }
        int[] ints = new int[k];
        for (int i = 0; i < k; i++) {
            ints[i] = arr[i];
        }
        return ints;
    }

    private void findKthSmallest(int[] arr, int l, int h, int k) {
        while(l < h){
            int j = partition(arr, l, h);
            if(k == j || k == j-1) break;
            if(k < j-1){
                findKthSmallest(arr,l,j-1,k);
            }else if(k > j){
                findKthSmallest(arr, j+1, h, k);
            }
            break;
        }
    }

    private int partition(int[] nums, int l, int h ){
        int i = l,j = h;
        while(true){
            while(i < h && nums[++i] <= nums[l]);
            while(j > l && nums[j] >= nums[l]){j--;};
            if(i >= j){
                break;
            }
            swap(nums,i,j);
        }
        swap(nums,l,j);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j]=t;
    }
}
